import ps1
import re
import sys

def alignSequences(S,T):
    m = len(S)
    n = len(T)
    
    V = list()
    for i in range(0,m+1):
        v = list()
        for j in range(0, n+1):
            v.append(0) 
        V.append(v)
        
    for i in range(0,m+1): V[i][0]= -i;
    for j in range(0,n+1): V[0][j]= -j;
        
    outSeq1 = ""; outSeq2 = "";
    totalScore = 0; s= [0,0,0];
    for i in range(1,m+1):
        for j in range(1,n+1):
            s[0] =  V[i-1][j-1] + score(S[i-1],T[j-1]);
            s[1] = V[i-1][j] + score(S[i-1],"-");
            s[2] =  V[i][j-1] + score("-",T[j-1]);
            maxscore = max(s)
            
            if(maxscore == s[0]):
                V[i][j] = V[i-1][j-1] + score(S[i-1],T[j-1]);
            elif(maxscore == s[1]):
                V[i][j] = V[i-1][j] + score(S[i-1],"-");
            else: 
                V[i][j] = V[i][j-1] + score("-",T[j-1]);
                
    print("Alignment Score: " + str(V[m][n])); print();
    
    
    
    
    # Now build the matched strings
    
    i = m; j = n; lengthmatch = 0;
    while(i>0 and j>0 ):
        s[0] =  V[i-1][j-1] + score(S[i-1],T[j-1]);
        s[1] = V[i-1][j] + score(S[i-1],"-");
        s[2] =  V[i][j-1] + score("-",T[j-1]);
        
        if(V[i][j]==s[0]):
            outSeq1 = S[i-1] + outSeq1; outSeq2 = T[j-1] + outSeq2; 
            if(S[i-1]==T[j-1]): lengthmatch = lengthmatch +1;
            i = i-1; j = j-1;
        elif(V[i][j]==s[1]):
            outSeq1 = S[i-1] + outSeq1; outSeq2 = "-" + outSeq2;
            i = i-1;
        elif(V[i][j]==s[2]):
            outSeq1 = "-" + outSeq1; outSeq2 =T[j-1] + outSeq2;
            j = j-1;    
            
    while(i>0):
        outSeq1 = S[i-1] + outSeq1;
        outSeq2 = "-" + outSeq2;
        i = i-1;
        
    while(j>0):
        outSeq1 = "-" + outSeq1;
        outSeq2 = T[j-1] + outSeq2;
        j = j-1;
        
    print("Seq1: " + outSeq1); print();
    print("Seq2: " + outSeq2); print();
    return lengthmatch/len(outSeq1)
    
         
    
        

        
        
    
   
    
                
                
            
            
        
    
  
def score(a,b):
    if(a==b): return 2;
    elif(a=="-" or b=="-"):  return -1;
    elif(a!=b): return -1;
    else: return 0;
    
    

S1 = "ACGCTAGTCG";  S2 = "TACGTATGATCG";
alignSequences(S1,S2);

Genes = ps1.readSeqsFromFile(sys.argv[1]);

for i in range(1,len(Genes)):
    f = alignSequences(Genes[0],Genes[i]);
    print("Similarity Score:" + str(f)); print();
    


   
    